#ifndef QUICK_SORT
#define QUICK_SORT
template<class Type,int Length>
//http://comic.sjtu.edu.cn/thucs/GD_jsj_002b/flash/chap10/10-3-4.swf
void QuickSort(Type (&array) [Length] ){
	QuickSort2(array,0,Length-1);	
}
template<class Type>
void QuickSort(Type array [] , int start , int end){
	if(start >= end)return;
	Type pivotVal = array [start];	
	int s = start , e = end;
	bool moveDirection = true; //true: from end to start
	                                                //false : from start to end
	while( s < e){
		if( !moveDirection && array[s] > pivotVal  ){
			array[e] = array[s];
			moveDirection = true;		
		}
		if(moveDirection && array[e] < pivotVal ){			
			array[s] = array[e];			
			moveDirection = false;		
		}
		if(moveDirection)--e;
		else ++s;
	}
	array[s] = pivotVal;
	QuickSort(array, start , s - 1 );
	QuickSort(array, s +1 , end);
}





template<class Type>
void QuickSort2(Type array [] , int start , int end){
	if(start >= end)return;
	Type pivotVal = array[start] , temp;
	int s = start, e = end + 1;
	while(s  < e){
		for(s = s + 1; s <= end ; ++s)
			if( array[s] >= pivotVal )break;

		for(e = e - 1; e >= start ; --e)
			if( array[e] <= pivotVal )break;

		if(s < e){ // swap
			temp = array[s];
			array[s] = array[e];
			array[e] = temp;
		}
	}	
	// set pivot Value
	array[start] = array[e];
	array[e] = pivotVal;

	QuickSort(array, start , e - 1 );
	QuickSort(array, s , end);
}
#endif